package jjn.daily;

import java.util.Scanner;

/**
 * @author Jiang Jining
 * @since 2023-07-20 22:53
 */
public class LeetCode918 {
    
    public int maxSubarraySumCircular(int[] nums) {
        int total = 0, maxSum = nums[0], curMax = 0, minSum = nums[0], curMin = 0;
        for (int num : nums) {
            curMax = Math.max(curMax + num, num);
            maxSum = Math.max(maxSum, curMax);
            curMin = Math.min(curMin + num, num);
            minSum = Math.min(minSum, curMin);
            total += num;
        }
        return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        int[] nums = new int[count];
        for (int i = 0; i < count; i++) {
            nums[i] = scanner.nextInt();
        }
        int maxSubarraySumCircular = new LeetCode918().maxSubarraySumCircular(nums);
        System.out.println("maxSubarraySumCircular = " + maxSubarraySumCircular);
    }
}
